Để loại bỏ những đối thủ tiềm năng, ông đã tiêu diệt những người anh em ruột của mình trong khoảng thời gian từ 1165-1171 [5]. Một trong số họ là Erke Qara đã trốn thoát và chạy sang bộ tộc Nãi Man - một bộ tộc lân cận ở phía tây của Khắc Liệt. Hai anh em khác, Buqa-Timur và Tai-Timur Taïshi đã bị xử tử. Tuy nhiên, thành công ban đầu của Thoát Lý rất ngắn ngủi vì chú của ông vốn được biết đến với tên Gurkhan đã lật đổ ông. Thoát Lý bỏ trốn cùng con gái và một số bề tôi trung thành. Ông đã cố gắng để giành sự hỗ trợ từ tộc Miệt Nhi Khất để lật đổ Gurkhan. Nhưng vị lãnh đạo của tộc Miệt Nhi Khất là Toqto'a Beki đã từ chối giúp đỡ mặc dù Thoát Lý đã hứa gã con gái mình cho Beki vì quân Khắc Liệt rất đông và mạnh để có thể đối phó, sau khi thất bại trong việc nhờ chi viện, Thoát Lý đến gặp cha của Thiết Mộc Chân là Dã Tốc Cai. Dã Tốc Cai đã quyết định giúp Thoát Lý vì trước đó ông đã từng chiến đấu với người Khắc Liệt chống lại người Tatars. Người Khắc Liệt đã rất ngạc nhiên khi Dã Tốc Cai tổ chức tấn công mà không có thời gian chuẩn bị. Mặc dù thực tà quân số Khắc Liệt đông hơn nhiều, nhưng lực lượng của họ đã bị phân tán khắp miền Trung Mông Cổ. Thoát Lý giành lại quyền lãnh đạo bộ tộc và Gurkhan đã bỏ trốn.

Mối quan hệ với Thiết Mộc Chân

Thoát Lý cùng với anh mình là Jakha Gambhu, Thiết Mộc Chân và Trát Mộc Hợp - anh em kết nghĩa của Thiết Mộc Chân đã cùng lãnh đạo liên minh chống lại người Miệt Nhi Khất khi Bột Nhi Thiếp-vợ của Thiết Mộc Chân bị bắt cóc vào năm 1183 [6]. Hai trong số các thủ lĩnh của Miệt Nhi Khất là Dair Usun và Toqto'a đã bỏ trốn trước đó, có lẽ do được báo cáo bởi những trinh sát đã thấy các đạo quân di chuyển. Liên quân dễ dàng giành chiến thắng trong cuộc giao tranh diễn ra sau đó và khoảng 300 người Miệt Nhi Khất đã thiệt mạng. Các thủ lĩnh đã chia nhau chiến lợi phẩm và trao những phụ nữ Miệt Nhi Khất cho các chiến binh. Những đứa trẻ bị biến thành nô lệ. Bột Nhi Thiếp được tìm thấy sau đó vào buổi tối. Thoát Lý đã trở lại trại của người Khắc Liệt cùng với người của mình, tự hào về một chiến thắng nhanh chóng.

Năm 1194, Thiết Mộc Chân có dự định tấn công liên minh Tatar - bộ tộc từ lâu đã gây ra cho ông nhiều vấn đề, bao gồm cả vụ mưu sát Dã Tốc Cai, ông đã cầu viện Thoát Lý và được chấp thuận khi vị Vương Hãn vẫn hài lòng với chiến thắng mà Thiết Mộc Chân đã có được trước đó. Ông nội của Thoát Lý là Marcus Buyruk Khan cũng từng bị ám sát bởi người Tatar, điều này cho ông một lý do tương tự với Thiết Mộc Chân để trả thù. Thoát Lý đã tham gia với Thiết Mộc Chân cùng vài nghìn quân Khắc Liệt. Người Jurkhin - một bộ tộc Mông Cổ, cũng được mời tham gia vào cuộc chiến nhưng từ chối lời đề nghị vì họ cũng có chút thù địch với tộc Bột Nhi Chỉ Cân (dòng dõi của Thiết Mộc Chân). Cuối cùng họ đã kết đồng minh với Hoàn Nhan Tương (完顏 襄) thừa tướng của Hoàng đế Kim Chương Tông của nhà Kim. Người Tatars đã bị người Nữ Chân coi là mối nguy hại và đây cơ hội là hoàn hảo để tiêu diệt chúng. Khi lực lượng liên hợp của Thoát Lý và Thành Cát Tư Hãn tấn công người Tatars, Người Tatars đã bị vây hãm trong một cuộc giao tranh vì các chiến binh Nữ Chân từ phía sau họ đã dễ dàng vây ráp kẻ thù. Đàn ông đã bị tàn sát, phụ nữ bị cướp làm vợ lẽ và trẻ em được nhận làm con nuôi hoặc trở thành người hầu, nô lệ. Khoảng hàng nghìn người Tatar đã kháng cự và tự mình trốn thoát. Đây là thời điểm mà Thoát Lý nhận được tôn hiệu Vương Hãn-.

Cuối năm đó, ông bị lật đổ bởi Erke Qara, người anh em mà ông đã không thể loại bỏ đã quay trở lại với quân đội Nãi Man. Nhiều người Khắc Liệt không hài lòng với sự trị vì của Thoát Lý nên đã hỗ trợ trong việc lật đổ ông. Thoát Lý chạy đến Tây Liêu với sự bảo hộ của Gia Luật Trực Lỗ Cổ [7] mà không hề tìm kiếm sự giúp đỡ của Thiết Mộc Chân. Theo bí sử Mông Cổ, ông đã ở lại đó một năm. Sau khi rời Tây Liêu, Thoát Lý quyết định gia nhập thế lực của Thành Cát Tư Hãn. Theo Rashid al-Din, ông đã đến được cứ điểm của Thành Cát Tư Hãn vào năm 1196. Thoát Lý đã trở thành khách của Thiết Mộc Chân trong khoảng hai năm.[8]